package com.acwing.partition12;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2022/1/14 9:36
 */
@SuppressWarnings("all")
public class AC1131拯救大兵瑞恩 {

    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static final int N = 11, M = N * N, E = 400, keyStatus = 1 << 10, INF = 0x3f3f3f3f, BASE = 131;
    private static int n = 0, m = 0, p = 0, k = 0, index = 0;
    //这里的type表示对应边的类型，是门还是墙，门的话又是哪种类型
    private static int[] head = new int[N * N], element = new int[E], next = new int[E], type = new int[E];

    //dp[i][j]表示在图上id为i的点，手中钥匙的状态为j的所花费的时间单位
    private static int[][] graph = new int[N][N], dp = new int[M][keyStatus];
    private static boolean[][] visited = new boolean[M][keyStatus];
    private static Set<Integer> edges = new HashSet<>();
    private static int[] key = new int[M];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        p = Integer.parseInt(s[2]);
        k = Integer.parseInt(reader.readLine());
        //给地图上每个位置一个唯一id
        for (int i = 1, id = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) graph[i][j] = id++;
        }
        for (int i = 0; i < N * N; i++) head[i] = -1;
        for (int i = 0; i < k; i++) {
            s = reader.readLine().split("\\s+");
            //读入边，c大于0则表示门的类型，(x1,y1)和(x2,y2)通过门相连；c等于0表示墙
            int x1 = Integer.parseInt(s[0]), y1 = Integer.parseInt(s[1]), x2 = Integer.parseInt(s[2]), y2 = Integer.parseInt(s[3]), c = Integer.parseInt(s[4]);
            int id1 = graph[x1][y1], id2 = graph[x2][y2];
            //表示这两条相连边已经用过，后续对没有建立出来的边创建
            edges.add(id1 * BASE + id2);
            edges.add(id2 * BASE + id1);
            if (c > 0) {
                createEdge(id1, id2, c);
                createEdge(id2, id1, c);
            }
        }
        //初始化图中其它没有指定的边
        init();
        int cnt = Integer.parseInt(reader.readLine());
        while (cnt-- > 0) {
            s = reader.readLine().split("\\s+");
            int x = Integer.parseInt(s[0]), y = Integer.parseInt(s[1]), c = Integer.parseInt(s[2]);
            //表示图上(x,y)有一把可以打开c类型门的钥匙，offset为1
            key[graph[x][y]] |= 1 << (c - 1);
        }
        writer.write(bfs(1, 0) + "\n");
        writer.flush();
    }

    private static void init() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (x == 0 || x > n || y == 0 || y > m) continue;
                    int id1 = graph[i][j], id2 = graph[x][y];
                    //如果这条边是门或者墙，在之前就已经创建过，就不需要进行处理，HashSet对于重复的元素不予操作
                    if (!edges.contains(id1 * BASE + id2)) createEdge(id1, id2, 0);
                }
            }
        }
    }

    private static int bfs(int start, int status) {
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], INF);
        dp[start][status] = 0;
        Deque<int[]> deque = new LinkedList<>();
        //加入初始状态，根据初始状态进行状态转移
        deque.addLast(new int[]{start, status});
        while (!deque.isEmpty()) {
            int[] pair = deque.pollFirst();
            int u = pair[0], curr = pair[1];
            if (visited[u][curr]) continue;
            visited[u][curr] = true;
            if (u == n * m) return dp[u][curr];
            //如果当前这个位置有钥匙，就捡起这些钥匙，并检查能更新的其它状态，也就是查看是否有可以松弛的边
            if (key[u] != 0 && dp[u][curr | key[u]] > dp[u][curr]) {
                dp[u][curr | key[u]] = dp[u][curr];
                deque.addFirst(new int[]{u, curr | key[u]});
            }
            for (int i = head[u]; i != -1; i = next[i]) {
                int v = element[i];
                //如果当前边有门隔断且没有钥匙，就无法继续
                if (type[i] > 0 && ((curr >> (type[i] - 1) & 1) == 0)) continue;
                //不是门或者有钥匙，就尝试更新下一个状态
                if (dp[v][curr] > dp[u][curr] + 1) {
                    dp[v][curr] = dp[u][curr] + 1;
                    deque.addLast(new int[]{v, curr});
                }
            }
        }
        return -1;
    }

    private static void createEdge(int u, int v, int c) {
        element[index] = v;
        next[index] = head[u];
        head[u] = index;
        type[index++] = c;
    }
}
